1. Field of the Invention
The present invention relates to a rolling stock scheduling apparatus and method of assigning all of a plurality of operations each having a predetermined departure time, departure site, arrival time, and arrival site to a plurality of available cars in consideration of operation limiting constraints and, more particularly, to creation of an initial plan that satisfies the constraints of a car operation.
2. Description of the Related Art
Many railway operators determine, for all train lines, the departure and arrival times from the departure site to the arrival site based on a train diagram. To actually operate trains, it is necessary to decide rolling stock sets (to be referred to as “cars” hereinafter) to be assigned to each series of line unit from a departure station to an arrival station on the train diagram (to be referred to as “train lines” hereinafter). Deciding the car assignment is called rolling stock scheduling.
In rolling stock scheduling, car assignment is done for each train line or a line group. The minimum unit of car assignment will be referred to as an “operation”.
Each operation has a predetermined departure time, departure site, arrival time, and arrival site. Every operation can be assigned to one of available cars in consideration of some operation limiting constraints. It is also possible to assign a plurality of operations to a single car in a single day without conflict.
According to “Railway Scheduling Algorithm” (Planning System Laboratory of Railway Technical Research Institute), rolling stock scheduling has the following constraints in general.
(1) Each car can depart from only its final arrival site of the day before. When a plurality of operations are assigned to a single car in a day, the second and subsequent operations to be assigned are limited to those starting from immediately preceding arrival sites (this constraint will be referred to as a “connection constraint” hereinafter).
(2) The difference in facility conditions between routes limits operable types of rolling stock.
(3) Operators have an obligation by law to periodically make inspections such as a general inspection, regular inspection, and daily inspection of each car.
(4) It is necessary to periodically ensure time for maintenance such as supply and cleaning of cars and passenger rooms.
In many cases, a scheduling plan that satisfies these constraints is made every predetermined period. This work is called “initial scheduling”. In this case, constraints associated with the initial day of schedule are newly imposed because connection to the immediately preceding period must be taken into consideration.
Operation disorder caused by, e.g., disorder in the schedule, or an urgent car work require a change of the original schedule. In this case, a schedule change that should allow to return to the original schedule as soon as possible is often made in consideration of the urgent situations. This work is called “rescheduling”. In rescheduling, it is necessary to restore the original schedule on the target day. For this reason, not only constraints associated with the initial day of schedule but also constraints associated with the place at which each car should arrive on the target day are separately imposed. The works of “initial scheduling” and “rescheduling” are called together “rolling stock scheduling”.
For the problem of rolling stock scheduling with the complex constraints, conventionally, many railway operators appoint a person in charge of scheduling, who often manually makes up a schedule based on his/her experiences and knowledge. Generally, initial scheduling is done to make a car roster as shown in FIG. 6 every predetermined period. Then, rescheduling is done, when the necessity arises.
Several automatic rolling stock scheduling techniques are disclosed. For example, the problem of rolling stock scheduling is modeled using a graph in which a train line is defined as a node, and a train line connectability as an arc (and identical train lines on different days are regarded as identical nodes). Circuits on the graph are obtained, thereby automatically making a periodical rolling stock scheduling plan. In another technique, the problem of rolling stock scheduling is modeled using a graph in which an operation is defined as a node, and an operation connectability as an arc. A genetic algorithm is used on the graph, thereby automatically making a scheduling plan that further increases an evaluation value. There is also disclosed still another technique associated with the problem of rolling stock scheduling, in which a periodical rotation pattern is created first. The pattern is changed as needed, thereby automatically making a scheduling plan (e.g., JP-A 2000-71988 (KOKAI)).
The procedure of initial scheduling or rescheduling by the person in charge of scheduling is based on trial and error. For this reason, the work is very time-consuming, and the quality of the schedule depends on the capability of the responsible person himself/herself. In addition, since the human work is not necessarily perfect, the schedule may be changed more than necessary by rescheduling, resulting in a large overhead of the change work. If a solution that should exist cannot be found, the operator is forced to take an emergency measure such as deadheading, transfer of operations, or vehicle exchange.
The conventional techniques can make a periodical or semi-periodical rolling stock scheduling plan but cannot cope with situations that often happen. An actual schedule is not periodical at all because it includes a schedule for weekdays and that for weekend and holidays, and the national holidays appear aperiodically. Additionally, the schedule can hardly be periodical because the constraints on the schedules of inspections and cleanings of cars is affected by the irregular schedule of each worker or a working site.
In the method of using a genetic algorithm on a graph, an initial solution is found, and solutions having high evaluation values are then successively generated from the initial solution. However, finding the initial solution itself is sometimes difficult. Solution is possible only in a simple problem with relaxed constraints. Finding the initial solution itself is very difficult especially in a problem with constraints that often appear in actuality, like a case that there are constraints associated with a place at which a car should arrive, a case that operation limiting constraints are strict, or a case that a plurality of operations are assigned to a single car in a single day, as in the problem to be solved by the present invention.
In the technique of the patent reference (e.g., JP-A 2000-71988 (KOKAI)) of creating a periodical rotation pattern, if a schedule does not satisfy constraints in the initial solution search stage or rescheduling stage for making a better schedule, a solution that satisfies the constraints is searched by backtrack search. However, this method only searches for a solution of one exchange between a car that does not satisfy the constraints and another car. A solution that satisfies the constraints is obtained by this simple method only in a simple case with relaxed constraints. In fact, it is impossible to obtain a solution in any problem to be described in the following embodiments of the present invention by this method. Additionally, the method of increasing the number of backtrack search conditions as the number of constraints increases, as described in this invention, is not preferable. This is because in an actual problem in which the constraints change every day, the maintenance cost of the backtrack search unit increases, resulting in difficult operations.
In the above-described prior arts, it is expected to be difficult to obtain a solution that satisfies the strict constraints of a car operation.